import { btPrint } from "hy-algokit";

export class Node<T> {
  value: T;
  left: Node<T> | null = null;
  right: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

export class TreeNode<T> extends Node<T> {
  // 当前节点的父节点（只用在搜索到再记录）
  parent: TreeNode<T> | null = null;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  // 判断当前节点是父节点的左子节点
  get isLeft(): boolean {
    return !!(this.parent && this.parent.left === this);
  }

  // 判断当前节点是父节点的右子节点
  get isRight(): boolean {
    return !!(this.parent && this.parent.right === this);
  }
}

class bsTree<T> {
  root: TreeNode<T> | null = null;

  // 打印二叉树
  print() {
    btPrint(this.root);
  }
  // 插入节点
  insert(value: T) {
    const newNode = new TreeNode<T>(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  // 递归插入节点
  insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  // 查找节点
  search(value: T): TreeNode<T> | null {
    let parent: TreeNode<T> | null = null;
    let current = this.root;
    while (current) {
      // 找到返回
      if (value === current.value) {
        return current;
      }
      // 没有找到继续往下找
      parent = current;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
      if (current) {
        // 有值记录父节点
        current.parent = parent;
      }
    }
    return null;
  }

  // 最小值
  minValueNode(): T | undefined {
    let current = this.root;
    if (current === null) {
      return undefined;
    }
    while (current.left) {
      current = current.left;
    }
    return current.value;
  }

  // 最大值
  maxValueNode(): T | undefined {
    let current = this.root;
    if (current === null) {
      return undefined;
    }
    while (current.right) {
      current = current.right;
    }
    return current.value;
  }

  // 先序遍历
  preOrderTraversal(node?: TreeNode<T> | null | undefined) {
    if (node === undefined) {
      node = this.root;
    }
    if (node === null) {
      return;
    }
    console.log(node.value);

    if (node.left) {
      this.preOrderTraversal(node.left);
    }
    if (node.right) {
      this.preOrderTraversal(node.right);
    }
  }

  // 中序遍历
  inOrderTraversal(node?: TreeNode<T> | null | undefined) {
    if (node === undefined) {
      node = this.root;
    }
    if (node === null) {
      return;
    }
    if (node.left) {
      this.inOrderTraversal(node.left);
    }
    console.log(node.value);
    if (node.right) {
      this.inOrderTraversal(node.right);
    }
  }

  // 后续遍历
  postOrderTraversal(node?: TreeNode<T> | null | undefined) {
    if (node === undefined) {
      node = this.root;
    }
    if (node === null) {
      return;
    }
    if (node.left) {
      this.postOrderTraversal(node.left);
    }
    if (node.right) {
      this.postOrderTraversal(node.right);
    }
    console.log(node.value);
  }

  // 层序遍历
  levelOrderTraversal() {
    if (this.root === null) {
      return;
    }

    let level: TreeNode<T>[] = [this.root];
    let nextLevel: TreeNode<T>[] = [];

    while (level.length > 0) {
      nextLevel = [];
      for (let i = 0; i < level.length; i++) {
        console.log(level[i].value);
        if (level[i].left) {
          nextLevel.push(level[i].left!);
        }
        if (level[i].right) {
          nextLevel.push(level[i].right!);
        }
      }
      level = nextLevel.length ? nextLevel : [];
    }
  }

   /** 实现删除操作 */
  remove(value: T): boolean {
    // 1.搜索: 当前是否有这个value
    const current = this.search(value)
    if (!current) return false

    // 声明替换树节点，替换需要删除的那个节点的父节点
    let replaceNode: TreeNode<T> | null = null
    if (current.left === null && current.right === null) { // 删除的是叶子节点
      replaceNode = null
    } else if (current.right === null) { // 删除的是有右子树的节点
      replaceNode = current.left
    } else if (current.left === null) { // 删除的是有左子树的节点
      replaceNode = current.right
    } else { // 删除的是有左右子树的节点,通过一个方法，不仅是获取右驱节点，还需要帮忙换好位置返回过来
      const successor = this.getSuccessor(current)
      replaceNode = successor
    }

    if (current === this.root) {
      this.root = replaceNode
    } else if (current.isLeft) {
      current.parent!.left = replaceNode
    } else {
      current.parent!.right = replaceNode
    }

    return true
  }
  // 通过后驱节点，移动指向达到删除delNode，返回以右驱节点为顶的节点树
    private getSuccessor(delNode: TreeNode<T>): TreeNode<T> {
    // 获取右子树
    let current = delNode.right
    let successor: TreeNode<T> | null = null
    while (current) {
      successor = current
      current = current.left
      if (current) {
        current.parent = successor
      }
    }

    // 拿到了后继节点
    if (successor !== delNode.right) {
      successor!.parent!.left = successor!.right
      successor!.right = delNode.right
    }

    // 一定要进行的操作: 将删除节点的left, 赋值给后继节点的left
    successor!.left = delNode.left

    return successor!
  }
}

const bst = new bsTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(14.5);
bst.insert(11.5);
bst.insert(12.5);
bst.insert(18.5);

bst.print();

// console.log("查找15", bst.search(15));
// console.log("查找122", bst.search(122));

// console.log("最小值", bst.minValueNode());
// console.log("最大值", bst.maxValueNode());

// console.log("先序遍历");
// bst.preOrderTraversal();

// console.log("中序遍历");
// bst.inOrderTraversal();

// console.log("后续遍历");
// bst.postOrderTraversal();

// console.log("层序遍历");
// bst.levelOrderTraversal();

console.log("删除3");
bst.remove(3);
bst.print();

console.log("删除9");
bst.remove(9);
bst.print();

console.log("删除13");
bst.remove(13);
bst.print();

console.log("删除15");
bst.remove(15);
bst.print();
